package leetcode_1000;

import java.util.ArrayList;
import java.util.List;
/**
 *@author 周杨
 *describe:寻找所有的N位正整数 每一位的相邻差值都位K 找出所有的这样的数字
 *回溯 AC 100%
 *2019年2月25日 下午7:27:01
 */
public class NumbersWithSameConsecutiveDifferences_967 {
	public static void main(String[] args) {
		NumbersWithSameConsecutiveDifferences_967 test = new NumbersWithSameConsecutiveDifferences_967();
		int[] res = test.numsSameConsecDiff(2, 1);
	}
	
	List<Integer> temp =new ArrayList<Integer>();
	public int[] numsSameConsecDiff(int N, int K) {
		if(K == 0) {//每一位都相同
			if(N == 1)  return new int[] {0,1,2,3,4,5,6,7,8,9};
			int ret[] = new int[9];
			for(int i=1;i<=9;++i) {
				int res =0 ,mul = 1,off = 1;
				while(off <= N) {
					res += mul*i;
					mul*=10;
					++off;
				}
				ret[i-1] = res;
			}
			return ret;
		}
		if(N == 1) {//只有1位 要吧0考虑进去
			List<Integer> t =new ArrayList<Integer>();
	        for(int i=0;i<=9;++i) {
	        	t.add(i);
	        	dfs(t,N,K);
	        	t.remove(t.size()-1);
	        }
		}else {
			List<Integer> t =new ArrayList<Integer>();
	        for(int i=1;i<=9;++i) {
	        	t.add(i);
	        	dfs(t,N,K);
	        	t.remove(t.size()-1);
	        }
		}
        int[] res = new int[temp.size()];
        for(int i=0;i<temp.size();++i)
        	res[i] = temp.get(i);
        return res;
    }
	
	public void dfs(List<Integer> list,int N,int K) {
		if(list.size() == N) {
			int mul = 1;
			int res = 0;
			for(int i = N-1;i >= 0; --i) {
				res += mul*list.get(i);
				mul*=10;
			}
			temp.add(res);
			return;
		}
		int i = list.get(list.size()-1);
		if(i+K < 10) {
			list.add(i+K);
			dfs(list,N,K);
			list.remove(list.size()-1);//回溯
		}
		if(i-K >= 0) {
			list.add(i-K);
			dfs(list,N,K);
			list.remove(list.size()-1);//回溯
		}
	}
}
